package com.bitongchong.nowcode;
//选择排序
public class Code_1_2_SelectSort {
	public static void selectSort(int [] arr) {
		//解题思路：从第一个数字开始，将它后面的数与它比对，设置第一个数字为min_index，如果后面有比它小的，交换位置
		//下一轮循环由下一个数开始（因为这个数字已经是最大或者是最小的了），知道最后一位
		if (arr == null || arr.length ==1) {
			return;
		}
		for (int i = 0; i < arr.length-1; i++) {
			//设置一个最小值，减少swap的次数，降低时间复杂度
			int minIndex = i;
			for (int j = i+1; j < arr.length; j++) {
				minIndex = arr[minIndex] > arr[j] ? j : minIndex;
			}
			swap(arr, i, minIndex); 
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
//		arr[i] = arr[i]^arr[j];
//		arr[j] = arr[i]^arr[j];
//		arr[i] = arr[i]^arr[j];
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		// 这儿为什么不能使用前一种交换方式呢？因为会出现自己和自己进行 ^ 操作，当i就是minIndex时，就会出现0的情况
		// 但是也可以添加一个如下的判断
		//	if (i == minIndex) {
		//		return;
		//	}
	}
	
	public static void main(String[] args) {
		int [] arr = new int [6];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (1000*Math.random());
		}
		selectSort(arr);
		for (int i : arr) {
			System.out.println(i);
		}
	}
}
